package com.thinkbig.editdistance;

import java.util.ArrayList;

public class LevenshteinDistance {

    /**
     * @param args
     */
    public static void main(String[] args) {
        String query = "我的祖国";
        ArrayList<String> list = new ArrayList<String>();
        list.add("abc");
        list.add("abbd");
        list.add("abce");
        list.add("abvf");
        list.add("我们的祖国");
        list.add("我国");
        
        for (String s : list) {
            if (getScore(query, s) < 0.3) {
                System.out.println(s);
            }
        }
    }
    
    public static double getScore(String src, String dest) {
        assert (src != null && dest != null);
        assert (src.length() != 0 && dest.length() != 0);
        
        int len = Math.max(src.length(), dest.length());
        return (double)(levenshteinDistance(src, dest) / (double) len);
    }
    
    public static int levenshteinDistance(String src, String dest)    {
        int[][] d = new int[src.length() + 1][dest.length() + 1];
        int i, j, cost;
        char[] str1 = src.toCharArray();
        char[] str2 = dest.toCharArray();

        for (i = 0; i <= str1.length; i++)
        {
            d[i][0] = i;
        }
        for (j = 0; j <= str2.length; j++)
        {
            d[0][j] = j;
        }
        for (i = 1; i <= str1.length; i++)
        {
            for (j = 1; j <= str2.length; j++)
            {

                if (str1[i - 1] == str2[j - 1])
                    cost = 0;
                else
                    cost = 1;

                d[i][j] =
                    Math.min(
                        d[i - 1][j] + 1,              // Deletion
                        Math.min(
                            d[i][j - 1] + 1,          // Insertion
                            d[i - 1][j - 1] + cost)); // Substitution

                if ((i > 1) && (j > 1) && (str1[i - 1] == 
                    str2[j - 2]) && (str1[i - 2] == str2[j - 1]))
                {
                    d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
                }
            }
        }

        return d[str1.length][str2.length];
    }

}
